import java.util.*;
public class Parenthesis {
    //判断左右括号是否匹配
    private static boolean isMatch(char left,char right){
        if(left=='('){
            return right==')';
        }
        return false;


    }
    public boolean chkParenthesis(String A, int n) {

        Deque<Character> stack=new LinkedList<>();
        for(int i=0;i<n;i++){
            //先让左括号入栈
            if(A.charAt(i)=='('){
                stack.push(A.charAt(i));
            }else{
                //如果是右括号
                if(stack.isEmpty()){
                    return false;
                }
                char left=stack.pop();
                char right=A.charAt(i);
                //把左括号取出来与右括号匹配
                if(!isMatch(left,right)){
                    //不匹配返回false
                    return false;
                }
            }
        }
        //遍历完毕栈为空，全都匹配，返回true
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }
}